{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 平衡二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# Given a binary tree, determine if it is height-balanced.\n",
    "\n",
    "# For this problem, a height-balanced binary tree is defined as:\n",
    "\n",
    "# a binary tree in which the depth of the two subtrees of every node never differ by more than 1.\n",
    "\n",
    "# Example 1:\n",
    "\n",
    "# Given the following tree [3,9,20,null,null,15,7]:\n",
    "\n",
    "# #    3\n",
    "# #   / \\\n",
    "# #  9  20\n",
    "# #   /  \\\n",
    "# #  15   7\n",
    "# Return true.\n",
    "\n",
    "# Example 2:\n",
    "\n",
    "# Given the following tree [1,2,2,3,3,null,null,4,4]:\n",
    "\n",
    "# #      1\n",
    "# #     / \\\n",
    "# #    2   2\n",
    "# #   / \\\n",
    "# #  3   3\n",
    "# # / \\\n",
    "# #4   4\n",
    "\n",
    "# Return false.\n",
    "\n",
    "#---------------------------- TreeNode ----------------------------------#\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self,x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "#--------------------------- CreatTree ----------------------------------#\n",
    "\n",
    "BTree = TreeNode(3)\n",
    "BTree.left, BTree.right = TreeNode(9), TreeNode(20)\n",
    "BTree.right.left, BTree.right.right = TreeNode(15), TreeNode(7)\n",
    "\n",
    "\n",
    "NotBTree = TreeNode(1)\n",
    "NotBTree.left, NotBTree.right = TreeNode(2), TreeNode(2)\n",
    "NotBTree.left.left, NotBTree.left.right = TreeNode(3), TreeNode(3)\n",
    "NotBTree.left.left.left = TreeNode(4)\n",
    "NotBTree.left.left.right = TreeNode(4)\n",
    "\n",
    "\n",
    "#-------------------------- Solution -----------------------------------#\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "def getDepth(tree):\n",
    "    if tree is None:return 0\n",
    "\n",
    "    left = getDepth(tree.left)\n",
    "    right = getDepth(tree.right)\n",
    "\n",
    "    return (left if left > right else right) + 1\n",
    "\n",
    "\n",
    "def solution(tree):\n",
    "\n",
    "    if tree is None:return True\n",
    "\n",
    "    left = getDepth(tree.left)\n",
    "    right = getDepth(tree.right)\n",
    "\n",
    "    if abs(left-right) > 1:return False\n",
    "    result = solution(tree.left) and  solution(tree.right)\n",
    "\n",
    "    return  result\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(solution(BTree))\n",
    "    print(solution(NotBTree))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "学习过了二叉查找树，想必大家有遇到一个问题。例如，将一个数组{1,2,3,4}依次插入树的时候，形成了图1的情况。有建立树与没建立树对于数据的增删查改已经没有了任何帮助，反而增添了维护的成本。而只有建立的树如图2，才能够最大地体现二叉树的优点。\n",
    "<img src=\"image/chapter05/BalancedTree.png\" width=550>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图二是一颗平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：一棵二叉树中<span class=\"girk\">每个节点的两个子树的深度相差不会超过1</span>，并且左右两个子树都是一棵平衡二叉树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 平衡因子：\n",
    "\n",
    "       左子树的高度减去右子树的高度。由平衡二叉树的定义可知，平衡因子的取值只可能为0,1,-1.分别对应着左右子树等高，左子树比较高，右子树比较高。如下图\n",
    "       \n",
    "<img src=\"image/chapter05/BBTree.jpg\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 失衡与调整"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从某种意义上来讲，平衡二叉树的创建是一个不断失衡与调整的过程。随着新的元素插入，树的平衡状态被打破。那么难点是如何将一棵不平衡的二叉树变成平衡二叉树。人们发现，平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 最小失衡子树:\n",
    "        在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的.\n",
    "         \n",
    "        在图7中。2结点（左子树树高-右子树树高）的绝对值=2。同理，3结点的平衡因子也为2.此时同时存在了两棵不平衡子树，而以3为根的树是最小的不平衡子树。我们只要将其以3为中心，将最小不平衡树向左旋转，即可得到平衡二叉树，如图8。\n",
    "         \n",
    "         \n",
    "<img src=\"image/chapter05/Figure78.jpg\" width=350>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面我们先用两个简单的例子来感受一下调整的方法。\n",
    "\n",
    "例1：右子树过高，向左旋转。步骤如下\n",
    "\n",
    "       i.  将2作为根结点\n",
    "\n",
    "       ii. 将1作为2的左孩子\n",
    "\n",
    "       iii.将2的左孩子作为1的右孩子（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "<img src=\"image/chapter05/Figure9.jpg\" width=300>\n",
    "\n",
    "\n",
    "例2：左子树过高，向右旋转。步骤如下\n",
    "\n",
    "       i.   将2作为根结点\n",
    "\n",
    "       ii.  将3作为2的右孩子\n",
    "\n",
    "       iii. 将2的右孩子作为3的左孩子（维护树的有序性，只是此处为NULL而已）\n",
    "       \n",
    "<img src=\"image/chapter05/Figure10.jpg\" width=300>\n",
    "\n",
    "例3：右子树过高，向左旋转。步骤如下\n",
    "\n",
    "      i.   将3作为根结点\n",
    "\n",
    "      ii.  将3的左孩子作为1的右孩子\n",
    "\n",
    "      iii. 将1作为3的左孩子\n",
    "\n",
    "<img src=\"image/chapter05/Figure11.jpg\" width=300>\n",
    "\n",
    "如上，我们发现，旋转之后树并没有恢复平衡。对比图9，我们发现，根的右子树不一致。\n",
    "\n",
    "　　在上面的三个例子我们可以看出，我们对不平衡的树进行旋转的时候，不仅需要考虑需要最小失衡子树的根结点的平衡因子，还要考虑根结点较高子树的根结点的平衡因子。如图9与图11中，较高子树都为右子树，右子树不同，旋转后有着完全不同的结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 失衡类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 左子树过高"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【１】LL型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在LL型的不平衡树中，我们首先找到最小不平衡子树，再以其根结点向右旋转。为何是向右旋转呢？应该不难理解，向右旋转后，相当于右边的子树树高增加了1，而左边的子树树高降低了1，而原本的树高之差为2,那么就能够将根的平衡因子就化为0.引用一下之前的图如下。旋转之后为“原来根结点的左孩子作为新的根结点”。\n",
    "\n",
    "\n",
    "i.   将2作为根结点\n",
    "\n",
    "ii.  将3作为2的右孩子\n",
    "\n",
    "iii. 将2的右孩子作为3的左孩子（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "<img src=\"image/chapter05/Figure12.jpg\" width=300>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【２】LE型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在这里需要说明的是，插入的时候，是不会出现LE的这种情况的。只有在删除的时候才会出现。下面对于为何插入不可能出现做一些个人见解。我们不妨假设存在LE的这种情况。如下。\n",
    "\n",
    "<img src=\"image/chapter05/Figure13.jpg\" width=200>\n",
    "\n",
    "假设我们刚插入的元素是1，那么原来的树已经不是平衡树。不可能。\n",
    "\n",
    "　　假设我们刚插入的元素是2.5，那么原来的树也不是平衡树，也不可能。所以说在插入的时候，是不会出现LE的这种情况的。而具体什么时候会出现呢，我们在删除的章节进行讲解。同理，不可能出现RE的情况，下面也不进行讨论。读者可以使用反证法自行验证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【３】LR型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于LR，要分为两步进行旋。旋转之后为“原来根结点的左孩子的右孩子作为新的根结点”。第一以较高子树的根，即1，为中心向左旋转。具体步骤如下。\n",
    "\n",
    "i. 将2的左子树作为1的右子树（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "ii.  将1作为2的左子树\n",
    "\n",
    "iii.  将2作为3的左子树\n",
    "\n",
    "<img src=\"image/chapter05/Figure14.jpg\" width=300>\n",
    "\n",
    "第二以原树的根，即3为中心，向右旋转。最后结果如下\n",
    "\n",
    "<img src=\"image/chapter05/Figure15.jpg\" width=120>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 右子树过高"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【１】RR型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是引用一下之前的例子。旋转的步骤如下。旋转之后为“原来根结点的右孩子作为新的根结点”。\n",
    "\n",
    "i.  将2作为根结点\n",
    "\n",
    "ii.  将1作为2的左孩子\n",
    "\n",
    "iii.  将2的左孩子作为1的右孩子（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "<img src=\"image/chapter05/Figure16.jpg\" width=350>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【２】RL型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是引用一下之前的例子。与LR型类似，我们需要进行两次旋转。旋转之后为“原来根结点的右孩子的左孩子作为新的根结点”。\n",
    "\n",
    "第一，以根结点的右孩子即3为中心向右旋转，结果如下。具体步骤如下\n",
    "\n",
    "i.  将2作为1的右孩子\n",
    "\n",
    "ii. 将3作为2的右孩子\n",
    "\n",
    "iii.将2的右孩子作为3的左孩子（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "<img src=\"image/chapter05/Figure17.jpg\" width=350>\n",
    "\n",
    "第二，以原根结点即1，作为中心，向左旋转。结果如下。具体步骤如下\n",
    "\n",
    "i.   将2作为根结点\n",
    "\n",
    "ii.   将1作为2的左孩子\n",
    "\n",
    "iii.   将2的左孩子作为1的右孩子（维护树的有序性，只是此处为NULL而已）\n",
    "\n",
    "<img src=\"image/chapter05/Figure18.jpg\" width=250>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
